//<p>给你一个非负整数数组 <code>nums</code> 和一个整数 <code>target</code> 。</p>
//
//<p>向数组中的每个整数前添加&nbsp;<code>'+'</code> 或 <code>'-'</code> ，然后串联起所有整数，可以构造一个 <strong>表达式</strong> ：</p>
//
//<ul> 
// <li>例如，<code>nums = [2, 1]</code> ，可以在 <code>2</code> 之前添加 <code>'+'</code> ，在 <code>1</code> 之前添加 <code>'-'</code> ，然后串联起来得到表达式 <code>"+2-1"</code> 。</li> 
//</ul>
//
//<p>返回可以通过上述方法构造的、运算结果等于 <code>target</code> 的不同 <strong>表达式</strong> 的数目。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [1,1,1,1,1], target = 3
//<strong>输出：</strong>5
//<strong>解释：</strong>一共有 5 种方法让最终目标和为 3 。
//-1 + 1 + 1 + 1 + 1 = 3
//+1 - 1 + 1 + 1 + 1 = 3
//+1 + 1 - 1 + 1 + 1 = 3
//+1 + 1 + 1 - 1 + 1 = 3
//+1 + 1 + 1 + 1 - 1 = 3
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [1], target = 1
//<strong>输出：</strong>1
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= nums.length &lt;= 20</code></li> 
// <li><code>0 &lt;= nums[i] &lt;= 1000</code></li> 
// <li><code>0 &lt;= negSum(nums[i]) &lt;= 1000</code></li> 
// <li><code>-1000 &lt;= target &lt;= 1000</code></li> 
//</ul>
//
//<div><li>👍 1931</li><li>👎 0</li></div>

#include <bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int n = nums.size();
        // pos - neg = sum - neg - neg = target => neg = (sum - target) / 2
        int neg = reduce(nums.begin(), nums.end()) - target;
        if (neg < 0 || neg % 2 != 0) {
            return 0;
        }
        neg /= 2;
        unordered_map<int, unordered_map<int, int>> memo;
        function<int(int, int)> backTrace = [&](int cur, int negSum) -> int {
            if (negSum > neg) return 0;
            if (cur == n) {
                return negSum == neg ? 1 : 0;
            }
            if (memo[cur].contains(negSum)) return memo[cur][negSum];
            return memo[cur][negSum] = backTrace(cur + 1, negSum) + backTrace(cur + 1, negSum + nums[cur]);
        };
        return backTrace(0, 0);
    }
};

//leetcode submit region end(Prohibit modification and deletion)


int main() {
    Solution s;
    vector<int> d = {1};
    s.findTargetSumWays(d, 2);
}
